//
// Created by Vincent_Vic on 2020/3/30.
//

#ifndef DATAORGANIZATION_HEAPSORT_H
#define DATAORGANIZATION_HEAPSORT_H

#include "MaxHeap.h"

template <typename T>
class HeapSort {
public:
    //版本1 简单排序
    void heapSort_V1(T arr[],int n){
        MaxHeap<T> maxHeap = MaxHeap<T>(n);
        for (int i = 0; i < n; ++i)  //将arr入二叉树堆
            maxHeap.insert(arr[i]);
        for (int i = n-1; i >= 0; --i)  //从小的到大排序
            arr[i] = maxHeap.extractMax();
    }

    //版本2 Heapify
    void heapSort_V2(T arr[],int n){
        MaxHeap<T> maxHeap = MaxHeap<T>(arr,n);
        for (int i = n-1; i >= 0; --i)  //从小的到大排序
            arr[i] = maxHeap.extractMax();
    }

    //版本3 原地堆排序
    void heapSort_V3(T arr[],int n){
        // heapify
        //(n-1) / 2 从叶子结点进行shiftDown
        for (int i = (n-1) / 2; i >= 0; --i)
            shiftDown(arr,n,i);
        //从最后一个不断向前，从堆取出最大值
        for (int i = n-1; i > 0; --i)  {
            std::swap(arr[0],arr[i]); //交换第一个与最后一个
            shiftDown(arr,i,0); //调整前面的值
        }
    }

    void shiftDown(T arr[],int n, int k){
        while( 2*k+1 < n){ //判断是否有左孩子就说明可以继续判断
            // 在此轮循环中，arr[k]arr[j]交换位置
            // 初始化为父节点与左孩子交换位置j
            int j = 2 * k + 1;
            //右孩子存在并且大于父节点，交换位置j改成右孩子
            if(j + 1 < n && arr[j+1] > arr[j]) j ++;
            //如果父节点大于等于要交换的节点，那么无需操作
            if( arr[k] >= arr[j] ) break;
            std::swap(arr[k], arr[j]); //调整位置
            k = j ; //进入子节点继续检查调整后的子节点
        }
    }
};


#endif //DATAORGANIZATION_HEAPSORT_H
